package swardToOffer.struct_3_linkedlist;

/**
 * @Author ChanZany
 * @Date 2021/5/21 8:38
 * @Version 1.0
 * <p>
 * 面试题18（一）：在O(1)时间删除链表结点
 * 题目：给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。
 * 思路：为了在O(1)的时间删除该节点，由于该链表为单向结构，无法直接从目标结点找到其previous节点并通过
 * node.previous.next = node.next的方式进行删除
 * 故考虑通过复制下一个节点的值覆盖当前节点，并删除下一个节点来达到同样的目的
 * node.var = node.next.var;
 * node.next = node.next.next;
 * 如果当前节点为尾节点，则还是只有采取第一种办法，遍历链表找到delNode的上一个节点并对delNode进行解绑
 */
public class DeleteNodeInList {
    public void delNode(ListNode head, ListNode delNode) {
        if (delNode == head) head = head.next;
        if (delNode.next!=null){
            delNode.val = delNode.next.val;
            delNode.next = delNode.next.next;
        }else {
            ListNode p = head;
            while (p.next!=delNode){
                p=p.next;
            }
            p.next = null;
        }

    }

    public static void main(String[] args) {
        DeleteNodeInList Main = new DeleteNodeInList();
        ListNode head = new ListNode(0);
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        head.next=node1;
        node1.next=node2;
        node2.next=node3;
        Main.delNode(head,node3);
        new PrintLinkedListReversely().printLNR(head);
    }
}
